This is an interactive visualization (in $\mathbb{R}^2$) of the main lemma in the paper A geometric inequality and the complexity of computing volume by György Elekes.

The lemma states that for any finite set $V \subset \mathbb{R}^n$, one has \[\text{conv}(V) \subset \bigcup_{v \in V} B(v/2, \vert\vert v \vert\vert/2)\]

where $B(x, r)$ is the ball of radius $r$ at $x$.

In the visualization, you can see how the convex hull of the points is contained in the yellow “balls” centered at the midpoint between each point and the origin.

Warning: The convex hull is not recalculated as the points move! Refresh the page to get a new set of points.

The lemma was not immediately obvious to me, but this visualization makes it clearer. For a hint, I drew out the perpendicular bisectors between the origin to the line segments of the hull, which coincides exactly with where the balls intersect when one point is not contained in the circle generated by the other.

I didn’t put the convex hull inside of a larger ball, but the theorem in the paper does. Suppose the convex hull were scaled down to be in the unit ball. Then each smaller ball would have radius at most $1/2$. This is true in each dimension, so each additional dimension decreases the relative volume of each smaller ball to the unit ball by at least a factor of $1/2$. So with $k$ points in $N$ dimensions, one has that the volume of the convex hull is bounded above by the volume of the smaller balls, $\frac{k}{2^N}$.

The paper goes on to show how this implies that one cannot have a polynomial time algorithm for estimating the volume of a convex hull up to a constant factor given a “well-guaranteed separation oracle”.

I came across this as Exercise 1.1 in Chapter 2 of Mathematics++ by Ida Kantor, Jiří Matoušek, and Robert Šámal. The authors mention that better bounds are known.

Code for the visualization is here: https://github.com/samzhang111/convexhullcircles. The library I used was JSXGraph, which does some really nice handling around all of the interactions.

I was not expecting to find anything this polished, but I did find it peculiar that 1) when I ran the Graham scan implementation they provide, it returns the raw coordinates for each point on the hull, rather than any usable reference back to the point objects themselves (which would be useful due to how the library sets up interactions), and 2) I couldn’t find documentation on how I would even begin to setup an event hook to redo the convex hull as the points move.